package com.zhugang.week04;

/**
 * @program algorithms
 * @description: waysToStep
 * @author: chanzhugang
 * @create: 2022/06/23 21:55
 */
public class WaysToStep {

    int mod = 1000000007;
    int[] mem = new int[1000001];

    /**
     * 三步问题
     *
     * @param n
     * @return
     */
    public int waysToStep(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        if (mem[n] != 0) return mem[n];
        // n - 1 和 n - 2 的和 求模  + (n - 3) 求模
        mem[n] = ((waysToStep(n - 1) + waysToStep(n - 2)) % mod + waysToStep(n - 3)) % mod;
        return mem[n];
    }


}